package leetcode.dynamic;

public class Lc213 {

    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0], nums[1]);
        if (n == 3) return Math.max(nums[0], Math.max(nums[1], nums[2]));
        //分两种情况dp。1;偷第一家 2：不偷第一家
        int[] dp1 = new int[n]; //dp[i] 代表偷到第i家最多能偷多少
        int[] dp2 = new int[n];
        //1.偷第一家
        dp1[0] = nums[0];
        dp1[1] = dp1[0];
        dp1[2] = nums[0] + nums[2]; //只有一种选择，偷第三家肯定是最多的
        for (int i = 3; i < n; i++) {
            if (i == n - 1) { //最后一家不能偷
                dp1[i] = dp1[i-1];
            } else dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
        }
        //2不偷第一家
        dp2[0] = 0;
        dp2[1] = nums[1];
        for (int i = 2; i < n; i++) {
            dp2[i] = Math.max(dp2[i-1], dp2[i-2] + nums[i]);
        }
        return Math.max(dp1[n-1], dp2[n-1]);
    }

}
